We consider large-scale sensor networks with n nodes, out of which k are inpossession, (e.g., have sensed or collected in some other way) k informationpackets. In the scenarios in which network nodes are vulnerable because of, forexample, limited energy or a hostile environment, it is desirable todisseminate the acquired information throughout the network so that each of then nodes stores one (possibly coded) packet and the original k source packetscan be recovered later in a computationally simple way from any (1 + \epsilon)knodes for some small \epsilon > 0. We developed two distributed algorithms for solving this problem based onsimple random walks and Fountain codes. Unlike all previously developedschemes, our solution is truly distributed, that is, nodes do not know n, k orconnectivity in the network, except in their own neighborhoods, and they do notmaintain any routing tables. In the first algorithm, all the sensors have theknowledge of n and k. In the second algorithm, each sensor estimates theseparameters through the random walk dissemination. We present analysis of thecommunication/transmission and encoding/decoding complexity of these twoalgorithms, and provide extensive simulation results as well
展开▼
